|
| creator |
Lange, Ralph
| | Dürr, Frank
| | Rothermel, Kurt
| | date |
2008-07
| | | | description |
Moving objects databases (MODs) store objects trajectories by
spatiotemporal polylines that approximate the actual movements given
by sequences of sensed positions. Determining such a polyline with
as few vertices as possible under the constraint that it does not
deviate by more than a certain accuracy bound epsilon from the
sensed positions is an algorithmic problem known as trajectory
reduction.
A specific challenge is online trajectory reduction, i.e. continuous
reduction with position sensing in realtime. This particularly is
required for moving objects with embedded position sensors whose
movements are tracked and stored by a remote MOD.
In this paper, we present Connection-preserving Dead Reckoning
(CDR), a new approach for online trajectory reduction. It
outperforms the existing approaches by 30 to 50%. CDR requires the
moving objects to temporally store some of the previously sensed
positions. Although the storage consumption of CDR generally is
small, it is not bounded. We therefore further present CDRM whose
storage allocation and execution time per position fix can be
adjusted and limited. Even with very limited storage allocations of
less than 1 kB CDRM outperforms the existing approach by 20 to 40%.
| |